package queue;

import java.util.Arrays;

class BSTreeData implements Comparable<BSTreeData>{
	protected Integer key;
	protected Object satelliteData;
	
	protected BSTreeData(Integer key){
		this.key = key;
		this.satelliteData = key;
	}
	@Override
	public int compareTo(BSTreeData obj){
		return this.key.compareTo(obj.key);
	}
	@Override
	public String toString(){
		return String.valueOf(this.key);
	}
	
	@Override
	public boolean equals(Object obj){
		return this.key.equals(((BSTreeData)obj).key);
	}
}
public class AVLTreeImpl implements BSTree<Integer, BSTreeData> {

	protected BSTreeData[] tree;
	
	public AVLTreeImpl() {
		//de inicio o tamanho eh 1. com a insercao da raiz, o array deve 
		//crescer para 3 para ser possivel armazenar null nos filhos da raiz. 
		tree = new BSTreeData[1];
	}

	/****** METODOS JA IMPLEMENTADOS *****/
	private void resize(){
		//o tamanho do array tem que satisfazer a equacao: 2^(h+2)-1 onde 
		//h eh a altura da arvore. se a altura diminui, o tamanho do array tambem 
		//diminui
		int h = this.height();
		int requiredSize = ((int)Math.pow(2,h+2))-1;
		if(tree.length !=  requiredSize){
			tree = Arrays.copyOfRange(tree, 0, requiredSize);
		}
	}
	//cresce o array para acrescentar mais um nivel
	private void addLevel(){
		int length = tree.length;
		int newLegth = 2*length+ 1;
		tree = Arrays.copyOfRange(tree, 0, newLegth);
	}
	//retorna o filho a esquerda do no indexado por i. 
	private int left(int i){
		return (i*2 + 1);
	}
	//retorna o filho a direita do no indexado por i. 
	private int right(int i){
		return (i*2 + 1) + 1;
	}
	//retorna o pai do no indexado por i. 
	private int parent(int i){
		return (i-1)/2;
	}
	//um no vazio eh representado por uma posicao no array desocupada
	private boolean isEmpty(int i){
		return tree[i] == null;
	}
	//uma folha contem ambos os filhos vazios
	private boolean isLeaf(int i){
		boolean resp = false;
		if(left(i) >= tree.length){ //array nao esta dimensionado para os filhos
			resp = tree[i] != null;
		}else if(right(i) < tree.length){ //array ta dimensionado para os filhos
			resp = (tree[left(i)] == null) && (tree[right(i)] == null);
		}
		
		return  resp;
	}
	
	//retorna o nivel de uma posicao(noh)
	//private int level(int position){
	//	 return (int)(Math.log10(position+1)/Math.log10(2));
	//}
	
	//move uma subarvore cuja raiz esta em oldPOsition para por um no de posicao para newPosition
	//esse metodo eh util para implementar as rotacoes
	private void moveSubTree(int oldPosition, int newPosition){
		while(newPosition > tree.length-1){
			this.addLevel();
		}
		//o mover pode ser para baixo ou para cima
		if(newPosition > oldPosition){ //se for para baixo entao faz bottom-up 
			if(!isEmpty(oldPosition)){ 
				moveSubTree(left(oldPosition), left(oldPosition) + (newPosition-oldPosition)*2);
				moveSubTree(right(oldPosition), right(oldPosition) + (newPosition-oldPosition)*2);
				tree[newPosition] = tree[oldPosition];
				tree[oldPosition] = null;
			}
		}else if (newPosition < oldPosition){ //se for para cima faz top-down
			if(!isEmpty(oldPosition)){ 
				tree[newPosition] = tree[oldPosition];
				tree[oldPosition] = null;
				moveSubTree(left(oldPosition), left(oldPosition) + (newPosition-oldPosition)*2);
				moveSubTree(right(oldPosition), right(oldPosition) + (newPosition-oldPosition)*2);
			}
		}
	}
	
	//faz uma rotacao a esquerda considerando o no na posicao position
	private void leftRotate(int position){
		if(!isEmpty(position)){
			if(!isLeaf(position)){
				int root = position;
				int pivot = right(position); //(Pivot = Root.OS)
				moveSubTree(left(root), left(left(root))); //desce para esquerda a sub-arvore a esquerda do root
				tree[left(root)] = tree[root]; //desce root pra a esquerda
				root = left(root);//atualiza a posicao do root (pra seu filho a esquerda) 
				moveSubTree(left(pivot), right(root));//(Root.OS = Pivot.RS) seta o novo filho a direita do root com filho esquerda do pivot
				moveSubTree(pivot, parent(pivot)); //(Root = pivot) e automaticamente (Pivot.RS=Root)
				resize(); //para o caso da rotacao diminuir a altura da arvore 
			}
		}
	}
	
	//faz uma rotacao a direita considerando o no na posicao position
	private void rightRotate(int position){
		//TODO implemente como o espelho do leftRotate.  
		if(!isEmpty(position)){
			if(!isLeaf(position)){
				int root = position;
				int pivot = left(position); //(Pivot = Root.OS)
				moveSubTree(right(root), right(right(root))); //desce para direita a sub-arvore a direita do root
				tree[right(root)] = tree[root]; //desce root pra a direita
				root = right(root);//atualiza a posicao do root (pra seu filho a direita) 
				moveSubTree(right(pivot), left(root));//(Root.OS = Pivot.RS) seta o novo filho a direita do root com filho esquerda do pivot
				moveSubTree(pivot, parent(pivot)); //(Root = pivot) e automaticamente (Pivot.RS=Root)
				resize(); //para o caso da rotacao diminuir a altura da arvore 
			}
		}
	}
	
	@Override
	public Integer maximumKey() {
		return maximumKey(0);
	}
	private Integer maximumKey(int position){
		Integer maximum = null;
		if(!isEmpty(position)){
			maximum = tree[position].key;
			Integer maximumRightChild = maximumKey(right(position));
			if(maximumRightChild != null){
				maximum = maximumRightChild;
			}
		}
		return maximum;
	}
	

	@Override
	public Integer minimumKey() {
		return minimumKey(0);
	}
	private Integer minimumKey(int position){
		Integer minimum = null;
		if(!isEmpty(position)){
			minimum = tree[position].key;
			Integer minimumLeftChild = minimumKey(left(position));
			if(minimumLeftChild != null){
				minimum = minimumLeftChild;
			}
		}
		return minimum;
	}
	@Override
	public int height() {
		//a altura eh calculada a partir da raiz
		return height(0);
	}
	private int height(int i){
		int resp = -1;
		if(i < tree.length){
			if(!isEmpty(i)){
				if(!isLeaf(i)){
					resp = 1 + greater(height(left(i)),height(right(i)));
				}else{
					resp = 0;
				}
			}
		}
		return resp;
	}
	private int greater(int x,int y){
		int resp = y;
		if(y < x){
			resp = x;
		}
		return resp;
	}

	@Override
	public boolean search(Integer key){
		return search(key,0);
	}
	private boolean search(Integer key, int position){
		boolean resp = false;
		
		if(position < tree.length){
			if(!isEmpty(position)){
				resp = tree[position].key.equals(key);
				if(tree[position].key < key){
					resp = search(key,left(position));
				}else if (tree[position].key < key){
					resp = search(key,right(position));
				}
			}
		}
		return resp;
	}

	private boolean isBalanced(){
		return isBalanced(0);
	}
	
	//diz se a arvore cuja raiz eh dada pela posicao position esta balanceada ou nao
	private boolean isBalanced(int position){
		boolean resp = true;
		if(!isEmpty(position)){
			if(!isLeaf(position)){
				resp =  (Math.abs(calculateBalance(position)) < 2) &&
					     isBalanced(left(position)) && 
					     isBalanced(right(position)); 
			}
		}
		return resp;
	}
	@Override
	public int size(){
		return size(0);
	}
	
	private int size(int position) {
		int resp = 0;
		if(position < tree.length){
			if(!isEmpty(position)){
				resp = 1 + size(left(position)) + size(right(position)); 
			}
		}
		
		return resp;
	}
	
	/************ METODOS A SEREM IMPLEMENTADOS *************/
	
	// calcula o balance de uma arvore cuja raiz eh dada pela posicao position
	private int calculateBalance(int position){
		int resp = 0; 
		//TODO Implemente esse metodo fazendo da diferenca de altura(height) entre filho a esquerda e a direita
		return resp;
	}
	
	//rebalanceia a arvore a partir de um no (posicao) aplicando rotacoes necessarias
	//note que esse metodo deve depois ir propagando ate chegar a raiz
	private void rebalance(int position){
		
	}
	
	@Override
	public void insert(Integer key, BSTreeData value){
		insert(key,value,0);
	}
	
	/**
	 * Este metodo precisa ser alterado para deixar a arvore AVL balanceada novamente
	 * @param key
	 * @param value
	 * @param position
	 */
	private void insert(Integer key, BSTreeData value, int position){
		if(position < tree.length){
			if(isEmpty(position)){
				tree[position] = value;
				resize();
			}else{
				if(key < tree[position].key){
					insert(key,value,left(position));
				}else if (key > tree[position].key){
					insert(key,value,right(position));
				}
			}
		}
	}

	@Override
	public void remove(Integer key){
		
	}

	@Override
	public BSTreeData[] preOrder(){
		//TODO
		return null;
	}

	public static void main(String[] args) {
		AVLTreeImpl tree = new AVLTreeImpl();
		int h = tree.height();
		int s = tree.size();
		tree.insert(1,new BSTreeData(1));
		h = tree.height();
		s = tree.size();
		tree.insert(4,new BSTreeData(4));
		h = tree.height();
		s = tree.size();
		tree.insert(8,new BSTreeData(8));
		h = tree.height();
		s = tree.size();
		tree.leftRotate(0);
		tree.rightRotate(0);
		tree.leftRotate(0);
		tree.insert(6,new BSTreeData(6));
		tree.rightRotate(2);
		tree.leftRotate(2);
		tree.leftRotate(0);
		tree.rightRotate(0);
		h = tree.height();
		s = tree.size();
	}
}
